1100E - Andrew and Taxi - CodeForces Solution

// 二分 我们无法确定最后一步是从那边逼近的。
// 有可能从合法的方向 也有可能是从非法方向。。
// 如果在二分框架里面迭代统计答案。。需要最后用边界值 再从新跑一遍。。！！！！
// 然后这题 提升了个认知。。
// 虽然有些点他是同层的。。也就是在top序里面 实际上是随机的位置。。
// 我们也可以认为 按照这个top序 下如果真的存在边 。。他是不会成环的！！！
// 然后 这题很奇怪的一个点。。我跑不成环的左边界。。然后再-1
// 按理说是可以的。。但是不知道为什么不行。。
// 可能是哪里细节也要改动。。？？？？？
// #include <bits/DEBUG.h>

#include <bits/stdc++.h>
using namespace std;
#define euyia ios::sync_with_stdio(0), cin.tie(nullptr)
#define endl '\n'
#define int long long
#define ar array<int, 2>
#define arr array<int, 3>
int mod = 998244353; //1e9+7;
int inf = 1e18;
const int N = 1e5 + 5;
int t, n, m, k;
vector<int> mp[N];

signed main()
{
    euyia;
#ifdef DEBUG
    freopen("../1.in", "r", stdin);
#endif
    // 然后这题 在top里面每次建图。。。也是开拓了视野。。。
    cin >> n >> m;
    vector<arr> a(m);
    int l = 0, r = 0;
    for (auto &[x, y, c] : a)
        cin >> x >> y >> c, r = max(r, c);
    // 然后这里有个大坑。。就是变量名 一定要注意 不要重复了！！！！！
    // 这里之前 mx 设置成x  然后枚举的时候里面也有个x。。。。草。。
    r++; //有些例子他是全部成环的。。。所以如果我们要枚举 不成环的左边界。就要超出最大值。
    vector<int> b(n + 1), ins(n + 1);
    auto bfs = [&](int mx)
    {
        queue<int> q;
        for (auto &[x, y, c] : a)
            if (c >= mx)
            {
                mp[x].push_back(y);
                ins[y]++;
            }
        for (int i = 1; i <= n; ++i)
            if (!ins[i])
                q.push(i);
        int cnt = 0;
        while (q.size())
        {
            int u = q.front();
            q.pop();
            b[u] = ++cnt;
            for (int &v : mp[u])
                if (!--ins[v])
                    q.push(v);
        }

        for (int i = 1; i <= n; ++i)
            ins[i] = 0, mp[i].clear();

        return cnt == n;
    };
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (bfs(mid))
            r = mid;
        else
            l = mid + 1;
    }
    bfs(l);
    vector<int> ans;
    for (int i = 0; i < m; ++i)
    {
        auto [x, y, c] = a[i];
        if (c < l && b[x] > b[y])
            ans.push_back(i + 1);
    }
    cout << max(0LL, l - 1) << " " << ans.size() << endl;
    for (auto &x : ans)
        cout << x << " ";
    cout << endl;
};